Spatial database systems operate to provide storage and processing of spatial objects. One special type of spatial database system is a geographical information system (GIS), which is configured to store and operate on geo spatial data, i.e., data relating to features on the Earth's surface
One useful operation on spatial data is to determine a topological relationship between spatial objects. Most of the topological relationships between spatial objects are expressible in terms of intersections of a boundary, an interior, and an exterior of one spatial object with a boundary, interior and exterior of another spatial object. For example, the topological relationship of ‘B inside A’ means that the interiors of objects A and B intersect and the exterior of object B intersects the interior of object A, but the boundary of object B does not intersect the boundary or the exterior of object A and the interior of object B does not intersect the boundary or the exterior of object A.
Performing these topological relationship queries quickly is one of the most important aspects of GIS and spatial database systems. A typical query could be one that requests the relationships between a query object such as a complex polygon and a large number of test objects. The query object, a complex polygon with thousands of line segments, could represent one of over a 1000 local regions within the U.S. and the test objects could represent the approximately 1 million highway segments in the U.S. This query could be performed by using a vertical line to sweep from left to right, intersecting the highway line segments of the test objects. However, a sweep line based algorithm can perform poorly for at least two reasons: (1) the very large number of test geometries; and (2) the complexity of test geometries and query geometries.
When there are a large number of test geometries, a system can organize test geometries using a spatial index to improve query performance. A filtering step uses the spatial index to return a candidate set and a refinement step determines the precise relationships for the objects in the candidate set.
When the complexity of the test geometries or query geometries is high, interior approximations and TR*-tree can help improve performance. Interior approximation determines whether a point or a minimum bounding rectangle (MBR) is inside an interior tile of a tessellated query polygon. The TR*-tree decomposes polygons into trapezoids and builds an R*-tree on these trapezoids to improve performance of an INTERSECTS operation.
Additionally, different types of test geometries such as multi-point, line, multi-line, polygon and multi-polygon pose challenges for topological queries against query polygons.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.